#include <iostream>
#include <cstdlib>
#include <sys/time.h>
#include "QuickSort.h"

/**
* @brief To test whether the library "QuickSort.h" can work and the efficiency.
* 
*/
#define N 30
#define M 10
#define CALTIME (end.tv_sec - start.tv_sec) * 1000 + (end.tv_usec - start.tv_usec) / 1000
using namespace std;

/**
* @brief To print out the elements of vector b.
* 
* @param b
*/
template <typename T>
void printout( vector<T> & b)
{
    int num = b.size();
    for (int i = 0; i < num; i++)
        cout << b[i] << " ";
    cout << endl;
}

/**
* @brief To calculate the average number of the array.
* 
* @param num, size
*/
int average(const int* num, const int size)
{
    int ave = 0;
    for (int i = 0; i < size; i++)
    {
    ave += num[i];
    }
    ave /= size;
    return ave;
}

/**
* @brief To test the function and compare the effeciency of two sort function.
* 
*/
int main()
{
    // Test for whether both quicksort algorithms can work.
    cout << "Test for random numbers." << endl;
    vector<int> a;
    for (int i = 0; i < N; i++)
        a.push_back( rand() % 100 );
    cout << "Before quicksort: " ;
    printout(a);
    vector<int> b = a;
    cout << "After quicksort (choose pivot by median3): " ;
    quicksortmedian3(b);
    printout(b);
    b = a;
    cout << "After quicksort (choose pivot by random): " ;
    quicksortrandom(b);
    printout(b);

    cout << "Test for decrease numbers." << endl;
    a.clear();
    for( int i = N; i > 0; i-- )
    {
        a.push_back( i );
        a.push_back( i );
    }
    cout << "Before quicksort: " ;
    printout( a );
    b = a;
    cout << "After quicksort (choose pivot by median3): " ;
    quicksortmedian3(b);
    printout(b);
    b = a;
    cout << "After quicksort (choose pivot by random): " ;
    quicksortrandom(b);
    printout(b);

    // Test for the efficiency
    struct timeval start, end;
    int med3ran[ M ], med3des[ M ], randran[ M ], randdes[ M ];
    int med3random, med3decrease, randrandom, randdecrease;
    vector<int> Store[ M ], X[ M ], Y[ M ];
    int whole;
    while(1)
    {
        cin >> whole;
        if( whole <= 0)
            break;
        
        cout << endl << "Total number of testing element is " << whole << endl;
        for( int k = 0; k < M; k++ )
        {
            Store[ k ].clear();
            for( int i = 0; i < whole; i++ )
            Store[ k ].push_back( rand() % 10000 );

            // Test for median3 pivot.
            X[ k ] = Store[ k ];
            gettimeofday( & start, nullptr );
            quicksortmedian3( X[ k ] );
            gettimeofday( & end, nullptr );
            med3ran[ k ] = CALTIME;

            Y[ k ].clear();
            for( int i = whole; i > 0; i-- )
                Y[ k ].push_back( i );
            gettimeofday( & start, nullptr );
            quicksortmedian3( Y[ k ] );
            gettimeofday( & end, nullptr );
            med3des[ k ] = CALTIME;

            // Test for random pivot.
            X[ k ] = Store[ k ];
            gettimeofday( & start, nullptr );
            quicksortrandom( X[ k ] );
            gettimeofday( & end, nullptr );
            randran[ k ] = CALTIME;

            Y[ k ].clear();
            for( int i = whole; i > 0; i-- )
                Y[ k ].push_back( i );
            gettimeofday( & start, nullptr );
            quicksortrandom( Y[ k ] );
            gettimeofday( & end, nullptr );
            randdes[ k ] = CALTIME;
        }

        med3random = average( med3ran, M );
        med3decrease = average( med3des, M );
        randrandom = average( randran, M );
        randdecrease = average( randdes, M );

        cout << "Choose pivot by median3:" << endl;
        cout << "Average time for random numbers: " << med3random << "ms" << endl;
        cout << "Average time for decrease numbers: " << med3decrease << "ms" << endl;

        cout << "Choose pivot by random:" << endl;
        cout << "Average time for random numbers: " << randrandom << "ms" << endl;
        cout << "Average time for decrease numbers: " << randdecrease << "ms" << endl;
    }

    return 0;
}